UVa/11675 - Happy friends/11675.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <list>
  19 #include <map>
  20 #include <set>
  21
  22 template <class T> string toStr(const T &x){ stringstream s; s << x; return s.str(); }
  23 template <class T> int toInt(const T &x){ stringstream s; s << x; int r; s >> r; return r; }
  24
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  27 #define D(x) cout << #x " = " << (x) << endl
  28
  29 #define assign(x, y) memcpy(x, y, sizeof(y))
  30
  31 const int MOD = 1000000007;
  32 const int MAXN = 35;
  33
  34 vector<int> g[MAXN];
  35 int day[MAXN];
  36
  37 int odd[MAXN][MAXN], even[MAXN][MAXN], T[MAXN][MAXN], C[MAXN][MAXN], ans[1][MAXN];
  38
  39 void mul(int A[MAXN][MAXN], int B[MAXN][MAXN], int C[MAXN][MAXN], int p, int q, int r){
  40   for (int i=0; i<p; ++i){
  41     for (int j=0; j<r; ++j){
  42       C[i][j] = 0;
  43       for (int k=0; k<q; ++k){
  44         C[i][j] += A[i][k] * B[k][j];
  45         C[i][j] %= MOD;
  46       }
  47     }
  48   }
  49 }
  50
  51
  52
  53 void exp(int A[MAXN][MAXN], int C[MAXN][MAXN], int n, int e){
  54   int TT[MAXN][MAXN];
  55   if (e == 0){
  56     for (int i=0; i<n; ++i){
  57       for (int j=0; j<n; ++j){
  58         C[i][j] = 0;
  59       }
  60       C[i][i] = 1;
  61     }
  62     return;
  63   }
  64
  65   if (e == 1){
  66     assign(C, A);
  67     return;
  68   }
  69
  70   exp(A, TT, n, e/2);
  71   assign(C, TT);
  72   mul(C, C, TT, n, n, n);
  73   assign(C, TT);
  74   if (e % 2 == 1){
  75     mul(C, A, TT, n, n, n);
  76     assign(C, TT);
  77   }
  78 }
  79
  80
  81 int main(){
  82   int Casos;
  83   cin >> Casos;
  84   for (int Caso=1; Caso<=Casos; ++Caso){
  85     int n, m, k, d;
  86     if (!(cin >> n >> m >> k >> d)) break;
  87     for (int i=0; i<n; ++i){
  88       g[i].clear();
  89       g[i].push_back(i);
  90       day[i] = -1;
  91     }
  92     while (m--){
  93       int u, v; cin >> u >> v;
  94       g[u].push_back(v), g[v].push_back(u);
  95     }
  96
  97     //find day of sum for each node
  98     queue<int> q;
  99     day[k] = 0;
 100     q.push(k);
 101     while (q.size()){
 102       int u = q.front(); q.pop();
 103       foreach(edge, g[u]){
 104         int v = *edge;
 105         if (day[v] == -1){
 106           day[v] = !day[u];
 107           q.push(v);
 108         }
 109       }
 110     }
 111
 112     //find odd/even matrices
 113     for (int j=0; j<n; ++j){
 114       for (int i=0; i<n; ++i){
 115         odd[i][j] = even[i][j] = 0;
 116       }
 117       foreach(edge, g[j]){
 118         int i = *edge;
 119         if (day[j] == 0){
 120           even[i][j] = 1;
 121         }else{
 122           odd[i][j] = 1;
 123         }
 124       }
 125       even[j][j] = odd[j][j] = 1;
 126     }
 127
 128     //D("odd"); For(i, 0, n){ For(j, 0, n) printf("%d ", odd[i][j]); printf("\n"); }
 129
 130     //D("even"); For(i, 0, n){ For(j, 0, n) printf("%d ", even[i][j]); printf("\n"); }
 131
 132
 133
 134     mul(odd, even, C, n, n, n);
 135     exp(C, T, n, d/2);
 136     assign(C, T);
 137
 138     if (d % 2 == 1){
 139       mul(C, odd, T, n, n, n);
 140       assign(C, T);
 141     }
 142
 143     D("C"); For(i, 0, n){ For(j, 0, n) printf("%d ", C[i][j]); printf("\n"); }
 144
 145     for (int j=0; j<n; ++j){
 146       ans[0][j] = 0;
 147     }
 148     ans[0][k] = 1;
 149
 150     mul(ans, C, T, 1, n, n);
 151
 152     printf("Case %d:", Caso);
 153     for (int j=0; j<n; ++j){
 154       printf(" %d", T[0][j]);
 155     }
 156     printf("\n");
 157   }
 158   return 0;
 159 }